package solution.liuyu2783.offer;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 剑指 Offer 40. 最小的k个数
 * 输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
 *
 */
public class Q40_TopK_E {

	/**
	 * 思路：
	 * 1、用快排最高效解决 TopK 问题：O(N)O(N)
	 * 2、堆：大根堆(前 K 小) / 小根堆（前 K 大),Java中有现成的 PriorityQueue
	 */
	public static void main(String[] args) {
		
		int[] arr = new int[] {4,5,1,3,2};
//		int[] result = Q40_TopK_E.getTopByPriorityQueue(arr, 3);
		int[] result = Q40_TopK_E.getTopByQuickSort(arr, 3);
		System.out.print(Arrays.toString(result));
	}
	
	/**
	 * 快排
	 */ 
	public static int[] getTopByQuickSort(int[] arr, int k) {
		arr = quickSort(arr, 0, arr.length -1);
		int[] result = new int[k];
       
        for(int i = 0; i < k; i++) {
        	result[i] = arr[i];
        }
		return result;
	} 
	
	public static int[] quickSort(int[] arr, int low, int high) {
		System.out.println("low = "+ low + ", high= "+ high);
		if(low < high) {
			//查找基准书
			int index = getBaseIndex(arr, low, high);
			quickSort(arr, low, index -1);
			quickSort(arr, index +1 , high);
		}
		return arr;
	}
	
	public static int getBaseIndex(int[] arr, int low, int high) {
		
		// 将数组最左端arrays[0]作为默认的基准值,将最左端的值放至基准值的坑内。
		// 此时arrays[0]没有值了，需要从最右端找到一个比基准值小的数填至[0]这个坑。
		// 再从左到右找到一个比基准值大的数填到刚才的坑。循环进行直到low=high
		// 将基准值填至刚才的low位置。再进行分治
		int base = arr[low];
		arr[low] = 0;
		System.out.println("== "+base + " "+ Arrays.toString(arr));
		while (low < high) {
			while(low < high && base <= arr[high]) {
				high--;
			}
			arr[low] = arr[high];
			arr[high] =0;
			while(low < high && arr[low] <= base){
				low++;
			}
			arr[high] = arr[low] ;
			arr[low] = 0 ;
		}
		if(low == high) {
			arr[low] = base;
		}
		return low;
	}
	
	/**
	 * 保持堆的大小为K，然后遍历数组中的数字，遍历的时候做如下判断：
	 * 1. 若目前堆的大小小于K，将当前数字放入堆中
	 * 2. 否则判断当前数字与大根堆堆顶元素的大小关系，如果当前数字比大根堆堆顶还大，这个数就直接跳过；
    	反之如果当前数字比大根堆堆顶小，先poll掉堆顶，再将该数字放入堆中。
	 */
	public static int[] getTopByPriorityQueue(int[] arr, int k) {
		if (k == 0 || arr.length == 0) {
            return new int[0];
        }
		// 默认是小根堆，实现大根堆需要重写一下比较器。
        Queue<Integer> pq = new PriorityQueue<>((v1, v2) -> v2 - v1);
        for(int i =0; i < arr.length; i++) {
        	if(pq.size() < k) {
        		pq.offer(arr[i]);
        	}else {
        		if(arr[i] < pq.peek()) {
        			pq.poll();
                    pq.offer(arr[i]);
        		}
        	}
        }
        //构建返回值
        int[] result = new int[k];
        int index=0;
        for(Integer a:pq) {
        	result[index++] = a;
        }
        return result;
	}
}
